/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30



␈↓ α∧␈↓α␈↓ ¬KANOTHER SAMEFRINGE

␈↓ α∧␈↓␈↓ αTThis SAMEFRINGE is simpler than those in the last two ␈↓↓Newsletter␈↓s:

␈↓ α∧␈↓(DE SAMEFRINGE (X Y)
␈↓ α∧␈↓       (OR (EQ X Y)
␈↓ α∧␈↓           (AND (NOT (ATOM X))
␈↓ α∧␈↓                (NOT (ATOM Y))
␈↓ α∧␈↓                (SAME (GOPHER X) (GOPHER Y)))))

␈↓ α∧␈↓(DE SAME (X Y)
␈↓ α∧␈↓       (AND (EQ (CAR X) (CAR Y))
␈↓ α∧␈↓            (SAMEFRINGE (CDR X) (CDR Y))))

␈↓ α∧␈↓(DE GOPHER (U)
␈↓ α∧␈↓       (COND ((ATOM (CAR U)) U)
␈↓ α∧␈↓             (T (GOPHER (CONS (CAAR U) (CONS (CDAR U) (CDR U)))))))

␈↓ α∧␈↓Here it is in a proposed LISP publication language:

␈↓ α∧␈↓␈↓↓samefringe[x, y] ← x ␈↓αeq ␈↓↓y ∨ [¬␈↓αat ␈↓↓x ∧ ¬␈↓αat ␈↓↓y ∧ same[gopher x, gopher y]]

␈↓ α∧␈↓↓same[x, y] ← ␈↓αa ␈↓↓x ␈↓αeq a y ∧ ␈↓↓samefringe[␈↓αd ␈↓↓ x, ␈↓αd ␈↓↓y]

␈↓ α∧␈↓↓gopher u ← ␈↓αif at a ␈↓↓u ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ gopher ␈↓αaa ␈↓↓u . [␈↓αda ␈↓↓u . ␈↓αd ␈↓↓u] ␈↓

␈↓ α∧␈↓␈↓ αT␈↓↓gopher␈↓␈αdigs␈α
up␈αthe␈α
first␈αatom␈α
in␈αan␈α
S-expression,␈αpiling␈α
up␈αthe␈α
␈↓↓cdr␈↓␈αparts␈α
(with␈αits␈αhind␈α
legs)
␈↓ α∧␈↓so␈αthat␈αindexing␈αthrough␈αthe␈αatoms␈αcan␈αbe␈αresumed.␈α Because␈αof␈αshared␈αstructure,␈αthe␈αnumber␈αof
␈↓ α∧␈↓new␈α∩cells␈α∩in␈α∩use␈α∩in␈α∪each␈α∩argument␈α∩at␈α∩any␈α∩time␈α∪(apart␈α∩from␈α∩those␈α∩occupied␈α∩by␈α∪the␈α∩original
␈↓ α∧␈↓expression␈αand␈αassuming␈αiterative␈αexecution)␈αis␈αthe␈αnumber␈α
of␈α␈↓↓car␈↓s␈αrequired␈αto␈αgo␈αfrom␈αthe␈αtop␈α
to
␈↓ α∧␈↓the␈α∞current␈α∞atom␈α∞-␈α∞usually␈α∞a␈α∞small␈α∞fraction␈α∞of␈α∞the␈α∞size␈α∞of␈α∞the␈α∞S-expression.␈α∞ If␈α∞an␈α∞argument␈α∞of
␈↓ α∧␈↓␈↓↓samefringe␈↓ is not elsewhere referenced, its top level is forgotten and subject to garbage collection.

␈↓ α∧␈↓␈↓ αTI␈αthink␈αthis␈αshows␈αthat␈α␈↓↓samefringe␈↓␈αis␈αnot␈αan␈αexample␈αof␈αthe␈αneed␈αfor␈αcoroutines,␈αand␈αa␈αnew
␈↓ α∧␈↓"simplest␈α
example"␈α
should␈α
be␈α
found.␈α
 There␈αis␈α
no␈α
benefit␈α
in␈α
merely␈α
moving␈α
information␈αfrom␈α
data
␈↓ α∧␈↓structure␈α
into␈αcontrol␈α
structure,␈α
and␈αit␈α
makes␈α
some␈αkinds␈α
of␈α
modification␈αharder.␈α
 Thus␈α
a␈αgame-
␈↓ α∧␈↓playing␈αalgorithm␈αthat␈αchooses␈αthe␈αmost␈α"cost-effective"␈αnode␈αof␈αthe␈αtree␈αto␈αextend␈αcan't␈αhave␈αthe
␈↓ α∧␈↓usual␈α
simple␈αrecursive␈α
structure.␈α A␈α
program␈α
with␈αonly␈α
assignments␈αand␈α
␈↓αgo␈α
to␈↓s␈αmay␈α
have␈αthe␈α
most
␈↓ α∧␈↓easily␈α∪modified␈α∪control␈α∪structure.␈α∪ Of␈α∩course,␈α∪elegance,␈α∪understandability␈α∪and␈α∪a␈α∪control␈α∩logic
␈↓ α∧␈↓admitting straightforward proofs of correctness are also virtues.

␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Computer Science Department
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓ARPANET: MCCARTHY@SU-AI

␈↓ α∧␈↓␈↓ ε|1␈↓ ∧



␈↓ α∧␈↓␈↓εThis draft of SAMEFR[F76,JMC]@SU-AI PUBbed at 15:43 on December 15, 1976.␈↓
















































␈↓ α∧␈↓␈↓ ε|2␈↓ ∧